package com.sjc.algorithm.tree;

import java.util.Arrays;

/**
 * @author by SangJiacun
 * @Date 2020/5/11 15:55
 */
public class MyBinaryHeap {

    public static void main(String[] args) {
        //            1
        //      3         8
        //  6      5    7    2
        // 9 10  0  11 12
        int[] array = new int[]{1,3,8,6,5,7,2,9,10,0,11,12};
//        upAdjuct(array);

        buildHeap(array);
        System.out.println(Arrays.toString(array)); //[0, 1, 2, 6, 3, 7, 8, 9, 10, 5, 11, 12]
    }

    /**
     * 上浮, 最小堆，
     * TODO 有问题，只能上浮最后1个叶子节点。
     * 从最后一个非叶子节点开始，即数组最后一位
     * @param array 待调整的堆
     */
    public static void upAdjuct(int[] array){
        int child = array.length-1;
        int parent = (child-1)/2;

        int temp = array[child];

        while(child>0 && temp < array[parent]){
            array[temp] = array[parent];
            child = parent;
            parent = (parent-1)/2;
        }
        array[child] = temp;
    }

    /**
     * 下沉,最小堆
     * @param array 待调整的堆
     * @param parent 要下沉的 父节点
     * @param length 堆的有效大小
     */
    public static void downAdjuct(int[] array,int parent, int length){
        int temp = array[parent];
        int child = parent*2 +1;
        while(child < length){
            // 如果有右孩子，且右孩子的值 小于 左孩子
            if(child+1 < length && array[child+1] < array[child]){
                child++;
            }

            if(temp <= array[child]){
                break;
            }

            array[parent] = array[child];
            parent = child;
            child = parent*2 +1;
        }
        array[parent] = temp;
    }

    /**
     * 使用"下沉" 构建二叉堆
     * @param array
     */
    public static void buildHeap(int[] array){
        for(int i=(array.length-2)/2; i>=0; i--){
            downAdjuct(array,i,array.length);
        }
    }

}
